// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

const int N = 1e2+50, M = 1e5+50;

int t, n;

struct Stone {
    int s, e, l;
    bool operator < (const Stone &other) const {
        return s * other.l < other.s * l;
    }
} dat[N];

int dp[N][M];


const int INF = 0x3f3f3f3f;

inline void update(int &a, int b) {
    a = max(a, b);
}


int main(int argc, char const *argv[]) {
    // code
    scanf("%d", &t);
    for (int kk=0; kk<t; ++kk) {
        scanf("%d", &n);
        for (int i=1; i<=n; ++i)
            scanf("%d%d%d", &dat[i].s, &dat[i].e, &dat[i].l);
        sort(dat+1, dat+n+1);

        for (int i=0; i<=n; ++i)
            memset(dp[i], 0, sizeof dp[i]);

        dp[0][0] = 0;
        for (int i=0; i<n; ++i) {
            Stone ns = dat[i+1];
            int w = ns.e;
            for (int j=0; j+ns.s<M; ++j) {
                update(dp[i+1][j], dp[i][j]);
                update(dp[i+1][j+ns.s], dp[i][j] + w);
                w -= ns.l;
                w = max(w, 0);
            }
        }
        int ans = 0;
        for (int i=0; i<M; ++i)
            update(ans, dp[n][i]);
        printf("Case #%d: %d\n", kk+1, ans);
    }
    return 0;
}
